import { CheckAns } from "./CheckAns";

namespace LeetCode0001TwoSum {

    namespace easy {
        // 直接运算
        export function twoSum(nums: number[], target: number): number[] {
            // 有效性检测
            if (!nums || nums.length < 2 || target == NaN)
                return [];
            // calc
            const aryLength: number = nums.length - 1;
            for (let i = 0; i < aryLength; i++) {
                for (let j = i + 1; j <= aryLength; j++) {
                    // 已获得一组有效解，直接结束
                    if (nums[j] + nums[i] == target) {
                        return [i, j];
                    }
                }
            }
            return [];
        };
    }

    namespace SortedArray {
        // 数组排序优化计算
        export function twoSum(nums: number[], target: number): number[] {
            // 有效性检测
            if (!nums || nums.length < 2 || target == NaN)
                return [];
            // 构造对象存储数值，以便于后续排序
            let aryMaxTag: number = nums.length - 1;
            let ary: { idx: number, value: number }[] = new Array();
            for (let idx = 0; idx <= aryMaxTag; idx++) {
                const value: number = nums[idx];
                ary.push({ idx, value });
            }
            // sort the array
            ary = ary.sort((a: any, b: any) => {
                return a.value - b.value;
            });
            // 筛选数组最大有效下标（超过目标数的数组值无意义）；需要考虑负整数以及0
            for (let i = aryMaxTag; i >= 0; i--) {
                if (ary[0].value + ary[i].value > target)
                    continue;
                // 已获得一组有效解，直接结束
                if (ary[0].value + ary[i].value == target) {
                    return [ary[0].idx, ary[i].idx];
                }
                else {
                    // 记录最大有效下标
                    aryMaxTag = i;
                    break;
                }
            }
            // calc (第一组已经不需要计算了)
            for (let i = 1; i <= aryMaxTag; i++) {
                for (let j = aryMaxTag; j > i; j--) {
                    if (ary[j].value + ary[i].value > target)
                        continue;
                    // 已获得一组有效解，直接结束
                    if (ary[j].value + ary[i].value == target) {
                        return [ary[i].idx, ary[j].idx];
                    }
                    else {
                        // 记录最大有效下标
                        aryMaxTag = j;
                        break;
                    }
                }
            }
            return [];
        };
    }

    namespace hashAry {
        // 不排序，减少排序的开销
        export function twoSum(nums: number[], target: number): number[] {
            // 有效性检测
            if (!nums || nums.length < 2 || target == NaN)
                return [];
            // 构造新数组辅助计算
            let aryCnt: number = nums.length - 1;
            let ary: Map<number, number> = new Map();
            // 填充hash数组并计算（减少循环次数）
            for (let i = 0; i <= aryCnt; i++) {
                // 计算出期待的值
                const want: number = target - nums[i];
                // 查找当前hash表中有无期待值
                if (ary.has(want)) {
                    //@ts-ignore
                    return [ary.get(want), i];
                }
                // 将未匹配成功数值存入hash表；作为key存储，减少查找复杂度
                ary.set(nums[i], i);
            }

            return [];
        };

        // 优化
        export function twoSum2(nums: number[], target: number): number[] {
            // 有效性检测
            if (!nums || nums.length < 2 || target == NaN)
                return [];
            // 利用数组的现有方法优化
            let ans: number[] = [];
            let ary: Map<number, number> = new Map();
            nums.every((v: number, i: number): boolean => {
                // 计算出期待的值
                const want: number = target - nums[i];
                // 查找当前hash表中有无期待值
                if (ary.get(want) != undefined) {
                    //@ts-ignore
                    ans = [ary.get(want), i];
                    return false;
                }
                // 将未匹配成功数值存入hash表；作为key存储，减少查找复杂度
                ary.set(v, i);
                return true;
            });

            return ans;
        };
    }

    // test
    const testData: { ary: number[], target: number, ans: number[] }[] = [
        { ary: [-1, -2, -3, -4, -5], target: -8, ans: [2, 4] },
        { ary: [2, 7, 11, 15], target: 9, ans: [0, 1] },
        { ary: [3, 2, 4], target: 6, ans: [1, 2] },
        { ary: [3, 3], target: 6, ans: [0, 1] }
    ];
    for (const data of testData) {
        const ans = hashAry.twoSum2(data.ary, data.target);
        CheckAns(data, ans);
    }
}
